package arithmetic.LeetCode.MaximumSubarray;

/**
 * @author zhangyanqi
 * @since 1.0 2018/1/4
 */
public class Solution {
    public int maxSubArray(int[] nums) {
        int ans = Integer.MIN_VALUE;
        int si = 0;//si
        int sj = 0;//sj
        int minSi = 0;

        for (int i = 0; i < nums.length; i++) {
            sj += nums[i];
            if (si < minSi) {
                minSi = si;
            }
            if (sj - minSi > ans) {
                ans = sj - minSi;
            }
            si+=nums[i];
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
    }
}
